'''
Created on Nov 8, 2009

@author: Owner
'''

import copy
import gamemodel.board
import gamemodel.player
import interface.ConsoleAgent

class CheckerState(object):
	'''
	classdocs
	'''

	def __init__(self):
		'''
		Constructor
		'''
		self.board = None
		self.current_player = None
		self.players = []
		self.round = 0
		self.cache_sucessor_moves = 0 # An impossible initial value
		self.cache_sucessor_states = 0 # An impossible initial value
	
	@staticmethod
	def constructNew(player0, player1):
		#set up the initial state of a game
		board = gamemodel.board.CheckerBoard.constructEmptyBoard()
		board.setPlayer0(player0)
		board.setPlayer1(player1)
		
		instance = CheckerState()
		instance.board = board
		instance.players = [player0, player1]
		instance.current_player = player0
		instance.board.reset()
		
		return instance;
	
	@staticmethod
	def constructEmpty(player0 = None, player1 = None):
		if player0 == None:
			player0 = gamemodel.player.CheckerPlayer('Kel\'Thuzad')
		if player1 == None:
			player1 = gamemodel.player.CheckerPlayer('Sylvanas')
			
		#set up the initial state of a game
		board = gamemodel.board.CheckerBoard.constructEmptyBoard()
		board.setPlayer0(player0)
		board.setPlayer1(player1)
		
		instance = CheckerState()
		instance.board = board
		instance.players = [player0, player1]
		instance.current_player = player0
		instance.board.clear()
		
		return instance;
	
	@staticmethod
	def constructWithBoard(board):
		raise NotImplementedError
		
		return;
	
	def getRound(self):
		return self.round;
	
	def getPlayers(self):
		return self.players;
	
	def getCurrentPlayer(self):
		return self.current_player
	
	def getBoard(self):
		return self.board
	
	def Successor(self):	
		#query cache
#		state = self
		
		if self.cache_sucessor_states != 0:
			return self.cache_sucessor_states
	
#		currentPlayer = self.getCurrentPlayer()
	
#		pieces = player.pieces
		checkerStateList = []
		checkerMoveList = self.successorMove()
		
		if checkerMoveList != None :
			for move in checkerMoveList :
				tmp_state = self.take_checker_move(move)
				checkerStateList.append(tmp_state)
		
		if checkerStateList != [] :
			self.cache_sucessor_states = checkerStateList
		else :
			self.cache_sucessor_states = None
		
		return self.cache_sucessor_states
	
	def take_checker_move(self, move):
		tmp_state = self.get_copy()
		tmp_board = tmp_state.board
		player = tmp_state.getCurrentPlayer()
		if player == tmp_state.board.getPlayer0() :
			otherplayer = tmp_state.board.getPlayer1()
		else :
			otherplayer = tmp_state.board.getPlayer0()
				
		totalSteps = len(move.list)
		#the condition that contains eating
		if totalSteps != 1 :		
			# first, change the position of the current player's piece.
			#original position
			x = move.list[0].original[0]
			y = move.list[0].original[1]		
#			print "x,y is",x,y
#			for piece in player.pieces:
#			print "piece's position is", piece.position
		
			#destination position
			i = move.list[totalSteps - 1].destination[0]
			j = move.list[totalSteps - 1].destination[1]
			originalPiece = tmp_board.getBoardPosition(x, y, player)
			currentPiece = None
			originalEqualToDestination = False
			if move.list[0].original != move.list[totalSteps - 1].destination :
				currentPiece = gamemodel.piece.CheckerPiece(player, i, j)
				currentPiece.king = originalPiece.king
				
				if player == self.board.getPlayer0() :
					tmp_board.player0.add_piece(currentPiece)
				else :
					tmp_board.player1.add_piece(currentPiece)
				
				for piece in player.pieces :
					if piece.position == [x, y] :
						player.pieces.remove(piece)		
				if player == self.board.getPlayer0() :
					for piece1 in tmp_board.player0.pieces :
						if piece1.position == [x, y] :
							tmp_board.player0.delete_piece(piece1)
				else :
					for piece1 in tmp_board.player1.pieces :
						if piece1.position == [x, y] :
							tmp_board.player1.delete_piece(piece1)
							
				tmp_board.setBoardPosition(x, y, player, None)
				
				
				tmp_board.setBoardPosition(i, j, player, currentPiece)
				
#				player.add_piece(currentPiece)
				
				
			
			else :
				originalEqualToDestination = True
				for piece in player.pieces :
					if piece.position == [x, y] :
						piece.king = True
								
			# then, eat the opponent player's pieces
			for number in range(totalSteps) :
				opponentPieceX = move.list[number].original[0] + (move.list[number].destination[0] - move.list[number].original[0]) / 2
				opponentPieceY = move.list[number].original[1] + (move.list[number].destination[1] - move.list[number].original[1]) / 2
				for piece in otherplayer.pieces :
					if piece.position == [9 - opponentPieceX, 9 - opponentPieceY] :
						otherplayer.pieces.remove(piece)	
							
				if otherplayer == self.board.getPlayer0() :
					for piece1 in tmp_board.player0.pieces :
						if piece1.position == [9 - opponentPieceX, 9 - opponentPieceY] :
							tmp_board.player0.delete_piece(piece1)
				else :
					for piece1 in tmp_board.player1.pieces :
						if piece1.position == [9 - opponentPieceX, 9 - opponentPieceY] :
							tmp_board.player1.delete_piece(piece1)
				
				tmp_board.setBoardPosition(9 - opponentPieceX, 9 - opponentPieceY, otherplayer, None)
				
				# besides, judge whether the current player's piece had
				# turned King
				if originalEqualToDestination != True :
					if move.list[number].original[1] == 9 or j == 9 :
						for piece in player.pieces :
							if piece.position == [i, j] :
								piece.king = True
					
						
			#discuss no move with eating or can only eat once
		else :
			#original position
			x = move.list[0].original[0]
			y = move.list[0].original[1]
			#destination position
			i = move.list[0].destination[0]
			j = move.list[0].destination[1]
			# eat once
			if abs(x - i) != 1 :
				# move the current player's piece to the destination
				originalPiece = tmp_board.getBoardPosition(x, y, player)
				currentPiece = gamemodel.piece.CheckerPiece(player, i, j)
				# Judge whether the piece is King or can turn into King
				if j == 9 or originalPiece.king != False :
					currentPiece.king = True
				
				for piece in player.pieces :
					if piece.position == [x, y] :
						player.pieces.remove(piece)	
				
				if player == self.board.getPlayer0() :
					for piece1 in tmp_board.player0.pieces :
						if piece1.position == [x, y] :
							tmp_board.player0.delete_piece(piece1)
				else :
					for piece1 in tmp_board.player1.pieces :
						if piece1.position == [x, y] :
							tmp_board.player1.delete_piece(piece1)
							
				tmp_board.setBoardPosition(x, y, player, None)
				
				
#				player.add_piece(currentPiece)
				
				if player == self.board.getPlayer0() :
					tmp_board.player0.add_piece(currentPiece)
				else :
					tmp_board.player1.add_piece(currentPiece)
					
				tmp_board.setBoardPosition(i, j, player, currentPiece)
					
				
				# the position of opponent player's piece and eat it
				opponentPieceX = x + (i - x) / 2
				opponentPieceY = y + (j - y) / 2
				for piece in otherplayer.pieces :
					if piece.position == [9 - opponentPieceX, 9 - opponentPieceY] :
						otherplayer.pieces.remove(piece)	
							
				if otherplayer == self.board.getPlayer0() :
					for piece1 in tmp_board.player0.pieces :
						if piece1.position == [9 - opponentPieceX, 9 - opponentPieceY] :
							tmp_board.player0.delete_piece(piece1)
				else :
					for piece1 in tmp_board.player1.pieces :
						if piece1.position == [9 - opponentPieceX, 9 - opponentPieceY] :
							tmp_board.player1.delete_piece(piece1)
				
				tmp_board.setBoardPosition(9 - opponentPieceX, 9 - opponentPieceY, otherplayer, None)
				
			else :
				# move the current player's piece to the destination
				originalPiece = tmp_board.getBoardPosition(x, y, player)
				currentPiece = gamemodel.piece.CheckerPiece(player, i, j)
				# Judge whether the piece is King or can turn into King
				if j == 9 or originalPiece.king != False :
					currentPiece.king = True
				
				for piece in player.pieces :
					if piece.position == [x, y] :
						player.pieces.remove(piece)		
				if player == self.board.getPlayer0() :
					for piece1 in tmp_board.player0.pieces :
						if piece1.position == [x, y] :
							tmp_board.player0.delete_piece(piece1)
				else :
					for piece1 in tmp_board.player1.pieces :
						if piece1.position == [x, y] :
							tmp_board.player1.delete_piece(piece1)
								
				tmp_board.setBoardPosition(x, y, player, None)
				
				
#				player.add_piece(currentPiece)	
				if player == self.board.getPlayer0() :
					tmp_board.player0.add_piece(currentPiece)
				else :
					tmp_board.player1.add_piece(currentPiece)
				tmp_state.board.setBoardPosition(i, j, player, currentPiece)
					
		
#		print "x, y is", x, y
#		print "is successful eat?", tmp_board.isEmpty(x,y,player)
#		print "i, j is", i, j
#		print "is successful move?", not(tmp_board.isEmpty(i,j,player))
#		print "current player", player
#		for piece1 in player.pieces :
#			print "current player's list of piece", piece1.position
#		print
#		print "other player", otherplayer
#		for piece2 in otherplayer.pieces :
#			print "other player's list of piece", piece2.position
#		print
#		
#		
		return tmp_state
						

	def successorMove(self):
		#query cache
		if self.cache_sucessor_moves != 0:
			return self.cache_sucessor_moves
		
		# set up some initial values
		# 'checkerMoveList' stores all the feasible moves that can be used
		# in the current turn
		player=self.getCurrentPlayer()
		pieces=player.pieces
		checkerMoveList = []
		tempCheckerMoveList = []
		maxLength = 0
		mandantory = False
		
		# iterating for all the pieces for calculating the possible
		# moves that can be used in the current turn.
		for piece in pieces:
			# judge whether the current piece is king or not,
			# which will decide the value of isKing in generateMove,
			# because a piece with 'King' property can move backwards
			# in the y-axis 
			if piece.king != False:
				# the value of mandatory is to record whether it exist
				# one or more 'mandantory' moves that will eat the opponent
				# player's piece(s), if yes, the value of mandantory will 
				# be set to 'True', and the other moves that can not eat at 
				# least one piece will not be take into calculation.
				results = self.generateMove(\
					piece.position[0], piece.position[1],\
					mandantory, isKing = True)
			else:
				results = self.generateMove(\
					piece.position[0], piece.position[1],\
					mandantory, isKing = False)
				# The formation of 'results' is (tempCheckerMoveList,
				# mandantory), the first one value stores the
				# move generated by the 'generateMove' function,
				# and the second one means that whether some
				# 'mandantory' move is be found.
			
			# if no 'mandantory' move, then all the possible(in another word,
			# 'trivial', which means those moves that can not eat at least one 
			# piece of the opponent player.) moves can be stored, until the 
			# 'mandantory' move firstly is found -- if so, then value of 
			# mandantory that is passed into generateMove function will be 
			# set to 'True', besides, all the 'trivial' moves will be cleared
			# up from tempCheckerMoveList. From now on, the generateMove function
			# will not try to find out the 'trivial' move any more.
			if mandantory == False :
				if results[1] == False :
					if results[0] != None :
						tempCheckerMoveList.extend(results[0])
				else :
					mandantory = True
					tempCheckerMoveList = []
					tempCheckerMoveList.extend(results[0])
			else :
				if results[0] != None :
					tempCheckerMoveList.extend(results[0])
		
		# the player must apply the move that eat the most pieces
		for moves in tempCheckerMoveList :
			if maxLength < len(moves.list) :
				checkerMoveList = []
				maxLength = len(moves.list)
				checkerMoveList.append(moves)
			else :
				if maxLength == len(moves.list) :
					checkerMoveList.append(moves)
		
		# It only for the convenience of passing into other function
		if checkerMoveList != [] :
			self.cache_sucessor_moves = checkerMoveList
		else :
			self.cache_sucessor_moves = None
		
		return self.cache_sucessor_moves 
		
		
					
	def generateMove(self, i, j, mandantory, isKing):
		# set up some initial values
		checkerMoveList = []
		board = self.board
		player=self.getCurrentPlayer()
		
		# First try to find out the 'mandantory' move. If it exists,
		# the searching for 'trivial' moves will not be run any more.
		# Two variable decides the process, 'checkerMoveList == []' for
		# current piece, and 'mandantory' for the rest pieces
		
		# 'r' stores the checkerMoveList obtained from generate_chained_moves
		r = self.generate_chained_moves(i, j, isKing)
		if r != None :
			checkerMoveList.extend(r)
			mandantory = True
		
		# search for the 'trivial' moves.
		if checkerMoveList == [] and mandantory != True :
			# a normal piece may only move to upper right and upper left
			# that is (x, y) = (i + 1, j + 1) and (i - 1, j + 1)
			# after summarizing, x = [i + 1, i - 1]
			#                    y = [j + 1, None]
			# If the piece with King property, it can be move to
			# lower right and left, so similarly,
			# 					 x = [i + 1, i - 1]
			#                    y = [j + 1, j - 1]
			x = [i + 1, i - 1]
			if isKing != False:
				y = [j + 1, j - 1]
			else:
				y = [j + 1, None]
			
			for coordinateY in y :
				# if the piece is not king, it is needless to calculate the 
				# lower direction in y-axis (y < i)
				if coordinateY == None :
					continue
				
				for coordinateX in x :
					# Then, restrict the boundary of (coordinateX, coordinateX)
					# cause the scale of the board is 0~9, either in x-axis or 
					# y-axis
					if coordinateX != 10 and coordinateX!= -1 \
					and coordinateY != 10 and coordinateY != -1 :
						# if the position of upper right/left have no piece, then
						# it exists a feasible 'trivial' move.
						if board.isEmpty(coordinateX, coordinateY, player) :
							# class 'CheckerMove()' is for doing the operation on
							# the feasible 'trivial' move.
							checker_move = CheckerMove()
							# (i, j)                     -> original position;
							# (coordinateX, coordinateY) -> destination position
							micro_move = MicroMove(i, j, coordinateX, coordinateY)
							checker_move.add_micro_move(micro_move)
							
							# all the feasible move will be attached on the checkerMovelist
							checkerMoveList.append(checker_move)
						
		return (checkerMoveList, mandantory)
			
	
	def generate_chained_moves(self, i, j, isKing, secondCall = False):
		# set up some initial values
		checkerMoveList = []
		board = self.board
		player = self.getCurrentPlayer()
		if player == self.board.getPlayer0():
			otherplayer = self.board.getPlayer1()
		else :
			otherplayer = self.board.getPlayer0()
		
		# This function if for searching the 'mandantory' move, which may be a 
		# chained move with several branches.
		
		# a normal piece may only eat to upper right and upper left
		# (x, y) = (i + 2, j + 2) and (i - 2, j + 2) are the positions
		# of one piece after 'eating' the opponent's piece 
		# after summarizing, x = [i + 2, i - 2]
		#                    y = [j + 2, None]
		# If the piece with King property, it can be move to
		# lower right and left, so similarly,
		# 					 x = [i + 2, i - 2]
		#                    y = [j + 2, j - 2]
		x = [i - 2, i + 2]
		if isKing != False:
			y = [j + 2, j - 2]
		else:
			y = [j + 2, None]
		
		for coordinateY in y :
			# if the piece is not king, it is needless to calculate the 
			# lower direction in y-axis (y < i)
			if coordinateY == None :
				continue
			
			for coordinateX in x :
				# Then, restrict the boundary of (coordinateX, coordinateX)
				# cause the scale of the board is 0~9, either in x-axis or 
				# y-axis
				if coordinateX < 10 and coordinateX > -1 \
				and coordinateY < 10 and coordinateY > -1 :
					piece = board.getBoardPosition((i + coordinateX) / 2 , (j + coordinateY) / 2, player)
					# the three restrict conditions whether can 'eat' or not:
					# 1. there is a piece in the path
					# 2. the piece should be a opponent piece
					# 3. the destination position should be empty

#					print "coordinateX, coordinateY",coordinateX, coordinateY
#					print board.isEmpty(coordinateX, coordinateY, player)
#					print "i,j",i,j
#					print board.isEmpty(i, j, player)
#					print piece.position
#					print piece.player
#					for piece1 in player.pieces:
#						print piece1.position,
#					print
					
					if piece != None and piece.player == otherplayer and\
					board.isEmpty(coordinateX, coordinateY, player):
						
						# first several lines are similar to searching for 'trivial' move
						checker_move = CheckerMove()
						micro_move = MicroMove(i, j, coordinateX, coordinateY)
						checker_move.add_micro_move(micro_move)
						
						# these lines below are for the recursive
						
						# change the state of the pieces
						# one value is newState return
						# 'newState' is the new state of the pieces on the board
						# 'turnKing' means whether the piece turn into king
						newState = self.take_micro_move(micro_move)
						if micro_move.destination[1] == 9:
							isKing = True
						# These two values will be passed into iteration.
						successor_moves = newState.generate_chained_moves\
						(coordinateX, coordinateY, isKing, secondCall = True)
						# one point may be a intermediate point, or terminal point.
						# if termination (successor_moves = False), then just append
						# the move to checkerMoveList;
						# if intermediate (successor_moves != False), then the
						# destination position of intermediate will be the original
						# position of a new recursive, just like it be used in the
						# 'merge_successor_moves'. and 'r' is a branch that contains
						# all the feasible 'mandantory move' of one piece.
						if successor_moves != False :
							r = checker_move.merge_successor_moves(successor_moves)
							checkerMoveList.extend(r)
						else :
							checkerMoveList.append(checker_move)
							
		# the discussion is suit for either intermediate point or terminal point.
		# if checkerMoveList is not empty, then return
		# if it is empty, then according to the value of 'secondCall', which is used
		# for judging whether it exists a recursive. If no iteration, then only return
		# 'None', otherwise, checkerMoveList should append the move of upper level.														
		if checkerMoveList != [] :
			return checkerMoveList
		else :
			if secondCall == True :
				return False
			else :
				return	
	
	def take_micro_move(self, micro_move):
		# set up some initial values
		newState = self.get_copy()
		board = newState.board
		player = newState.getCurrentPlayer()
		if player == board.getPlayer0() :
			otherPlayer = board.getPlayer1()
		else :
			otherPlayer = board.getPlayer0()
		ori = micro_move.original
		des = micro_move.destination
		
		# delete the position in the original position and add it to the
		# new position
		piece = board.getBoardPosition(ori[0], ori[1], player)
		pieceNew = gamemodel.piece.CheckerPiece(player, des[0], des[1])
		if des[1] == 9 or piece.king == True:
			pieceNew.king = True
#		player.add_piece(pieceNew)
		newState.board.setBoardPosition(des[0], des[1], player, pieceNew)
#		player.delete_piece(piece)
		newState.board.setBoardPosition(ori[0], ori[1], player, None)

		# kill the opponent's piece
		mid = [(des[0] + ori[0]) / 2, (des[1] + ori[1]) / 2]
		
		
		for piece in otherPlayer.pieces :
			if piece.position == [9 - mid[0], 9 - mid[1]] :
				otherPlayer.pieces.remove(piece)	
							
			if otherPlayer == self.board.getPlayer0() :
				for piece1 in newState.players[0].pieces :
					if piece1.position ==[9 - mid[0], 9 - mid[1]] :
						newState.players[0].pieces.remove(piece1)
			else :
				for piece1 in newState.players[1].pieces :
					if piece1.position == [9 - mid[0], 9 - mid[1]] :
						newState.players[1].pieces.remove(piece1)
				
		newState.board.setBoardPosition(9 - mid[0], 9 - mid[1], otherPlayer, None)

#		If need, use the commands below to print the created board	
#		print
#		interface.ConsoleAgent.ConsoleDescriptor.drawState(newState)

#		for piece1 in player.pieces :
#			print "current player's list of piece", piece1.position
#		print
#		print "other player", otherplayer
#		for piece2 in otherplayer.pieces :
#			print "other player's list of piece", piece2.position
		
		return newState
		
	def get_copy(self):
		instance_copy = copy.deepcopy(self)
		instance_copy.cache_sucessor_moves = 0
		return instance_copy
	
	def switchPlayer(self):
		if self.current_player == self.board.getPlayer0():
			self.current_player = self.board.getPlayer1()
		else :
			self.current_player = self.board.getPlayer0()		
					
	
class CheckerMove(object):
	
	def __init__(self):
		self.list = []
	
	def add_micro_move(self, micro_move):
		self.list.append(micro_move)	
		

	def merge_successor_moves(self, checkerMoves):
		if checkerMoves == None:
			return [self]
		
		r = []
		
		for checker_move in checkerMoves:
			tmp_copy = copy.deepcopy(self)
			tmp_copy.list.extend(checker_move.list)
			r.append(tmp_copy)
		
		return r
	
	def getLength(self):
		return len(self.list)
	
	@staticmethod
	def constructByMicroMoves(micro_moves):
		instance = gamemodel.state.CheckerMove()
		
		for micro_move in micro_moves:
			instance.add_micro_move(micro_move)
		
		return instance


class MicroMove(object):
	
	def __init__(self,x1,y1,x2,y2):
		self.original = (x1,y1)
		self.destination = (x2,y2)
	
	def __eq__(a , b):
		if not isinstance(b, MicroMove):
			return False
		return a.original == b.original and a.destination == b.destination